Fraud Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities
light clientsが十分な数のhonestなnodesに対してfroud proofを問い合わせることで、full clientsとほぼ同等の「そのブロックに対する正当性」を得る。
パブリッシュされたデータはそのデータがfaultであることを意味していないのでdata availabilityは解決しない。
ただ、もし仮にfraudかつdata availability proofが提供できれば、light clientsにとってhonest-majority assumptionではなく、データをrebroadcastする最小数のhonestなnodes assumptionに帰着される。
ナイーブな解決策としては、ネットワークのあるlight clientのデータがunavailabilityであることを想定して、全てのlight clientsが検証してからそのブロックを正当とすること。
例えば、ブロックデータの一部のchunksをmerkle rootを利用して検証することで確率的にそのブロックがavaiableであることを示すことが可能。
しかし、例えば数百bytes程度のデータをwithholdする攻撃などは上記の確率的検証をすり抜けてしまう可能性が高い。
この問題を解決するためにerasure codesを用いる。（リードソルモンによる符号が代表的）
Merkle rootをextended dataとしてコミットし、light clientsが確率的に大多数のextended dataがavailableか検証する。
もしextended dataがavailableであれば、
erasure codeが正しく生成し、ブロックが正当なパターン。
erasure codeが正しく生成し、ブロックが不正なパターン→fraud proofをリレー。
erasure codeが正しく生成しない。→これを示すfraud proofをリレー。
問題定義・背景
ブロックチェーンの検証問題は長期的に見ると大きな問題
分散性低下によるセキュリティ低下
full nodes運営のインセンティブ
トランザクション
coda
snarksを用いてblockchain dataを固定
ステート
stateless clients
userに負荷
sleeping/awaking
state保持のためのfee
light clientにfull nodeとほぼ同等レベルのブロックチェーン検証能力を持たせるための設計提案
light clientはTxデータが正当であるか検証できない
shardsごとの検証
super-full node
top-level node
single-shard node
light node
https://gyazo.com/c528b89081503353324491b7e73fb03a
fullnodesはblockのTxデータを用いてpre-state rootからpost-state rootに遷移したか検証することができる
.$ VerifyTransitionFraudProof()関数の実行 - fraud proof
不正なブロック生成者はfull nodesがdataRootを計算するために必要なデータをwithholdし、fraud proofの生成を防ぐことでができてしまうのでfraud proofだけだとlight clientは厳しい
dataが本当にないのか、あるけど「ない」と言っているのか
light clientが全てのTx dataがavailableであること（Tx dataがdataRootにマッチすること）を検証する方法が必要
リード・ソルモン符号（Reed-Solomon Coding)
符号の生成と復号が複雑なので処理速度が比較的遅い反面、訂正能力が高い誤り訂正符号の一種。
有限体上において、k個のTx dataがあればy座標がその値となるk+1次多項式を生成し、その多項式上にk個のTx dataを載せることでデータをextend。
2k個のうちk個以上が集まればラグランジュの補間公式・高速フーリエ変換で多項式復元可能
rビット(以下r=8bitsを想定)の連続した固まりを１つのシンボルとし、k個のシンボルが実際に送る情報(merkle rootに相当）、残りのn-k個のシンボルが符号化で生成される冗長シンボルとする。
$ t = \frac{n-k}{2}とすると、t個までのシンボルの誤りを訂正可能。
標数2の8次拡大体上において上記のk個のリスト$ x_0, x_1,...,x_{k-1}が多項式P(x)上の点とし、拡張した$ x_k, x_{k+1}, ..., x_{n-1}もP(x)上の点とする。ラグランジュの補間公式（あるいは高速フーリエ変換）によりn個の中からk個のシンボルでPを復元することができる。
1D Reed-solomon
strawman data availability scheme
light clientsはfull nodesに少数のdataとそのmerkle proofをランダムに要求し、merkle rootを用いて検証する。
十分な数のlight clientに検証が行われれば確率的にかなりavailableである可能性が高い。
全dataのうち、ごく少しのdataをunavailableにするとランダムサンプリングによる検証が適用しにくくなる。
ごく一部のoriginalデータをunavailableにすると、Reed-solmonで復元するextended dataは異なり、ランダムサンプリングでavailability proofを適用できる。
少なくunavailableにすればerasure codeによりfraud proofが生成できる。
ブロック生成者はk個のトランザクションをリードソルモンを使って2k個にextendし、そのデータから生成したマークルルートをブロックヘッダーに含める。
light clientsはfull nodesにシェアをリクエストし、dataRootと全て一致するか検証。
十分な数のlight clientsがいないとサンプリングするシェアが少なくなり、安全性は低下する。
悪意のあるブロック生成者が不正にdataをextendすると、50％以上のdataがavailableでもブロックを復元することができない。
extended dataが不正かどうかのfraud proofはオリジナルのdataであり、受け取ったextended dataからのdataRootとマッチするか検証するためにローカルでエンコーディングするので、ブロックサイズに線形的に計算量が増えてしまう。
2D Reed-solomon matrix
https://gyazo.com/82d56366a12366955b96fe4cd6b1751d
Therefore, we instead use multi-dimensional encoding, as described in Section 5.2, so that proofs of incorrectly generated codes are limited to a specific axis—rather than the entire data—reducing proof size to O( d√ n) where d is the number of dimensions of the encoding.
1Dでは、$ x=0, x=1 ... x=kでラグランジュしていたのに対し、2Dでは、$ (x=0, y=0) ... (x=\sqrt{k}, y=\sqrt{k})でラグランジュ。
多項式の次数がより低くなるので計算複雑性の低下。
x
light clientsのfull nodesへの検証
1. full nodesからblock headerとrowRoots、ColumnRootsを受け取る
dataroot = root(rowRoots, ColumnRoots)か
2. 1つ以上のランダムな(x, y)をfull nodesに送る
3. その(x, y)に対応する全てのシェアとそのmerkle proof、(row or column)を送る
4. light clientsは保持しているmerkle rootsを使って検証
5. それぞれのシェアとmerkle proofを持っていない接続しているfull nodesにgossip。
6. そのブロックのerasure codeに対するfraud proofが一定時間内になければ、blockはlight clientに保存
Snarks/Starksの応用
merkle rootが正しく計算されているか、状態遷移が正しく行われているか証明
$ (prevStateRoot, txRoot, postStateRoot, proof, sig...)がblock headerとすると、proofがtxRootが正しいか、prevStateRootからpostStateRootが正しいかを証明。
ブロックを検証するためにはヘッダーのみをダウンロードし、proofを検証し、erasure coded dataのmerkle branchをランダムサンプリングにより検証。
（他のSTARKsの正当性をSTARKsを使って証明するrecursive STARKsによりerasure coded dataが生成できるかも（？））
制限
少なくともひとつのhonestなfull nodesに接続していることが前提
data availability proofのために十分安全なlight clients数
https://gyazo.com/9903fba266c5593046708827338c8a5a
BenchMark
Size of light client proof (1 MB): 48 branches * (256 bytes + 6 Merkle tree intermediate hashes * 32 bytes per hash) + (128 Merkle roots * 32 bytes per hash) = 25600 bytes
Size of light client proof (4 MB): 48 branches * (256 bytes + 7 Merkle tree intermediate hashes * 32 bytes per hash) + (256 Merkle roots * 32 bytes per hash) = 31232 bytes
Time spent to encode in C++ (1 MB): 7.5 seconds
Time spent to encode in C++ (4 MB): 43.45 seconds
Time spent to verify fraud proof (1 MB): < 0.01 seconds
Time spent to verify fraud proof (4 MB): < 0.01 seconds
Maximum size of fraud proof (1 MB): 6 Merkle tree intermediate hashes * 32 bytes per hash * 64 elements = 12288 bytes
Maximum size of fraud proof (4 MB): 7 Merkle tree intermediate hashes * 32 bytes per hash * 128 elements = 28672 bytes